package com.demoworld;

import org.junit.Test;

/**
 * Created by francis on 2017/7/5.
 */
public class QuickSortTest {

    @Test
    public void test1() {
        int[] arr = new int[]{1, 4, 76, 12, 23, 67};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i <= arr.length - 1; i++) {
            System.out.println(arr[i]);
        }
    }

    @Test
    public void test2() {
        int[] arr = new int[]{1, 4, 76, 12, 23, 67, 3};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i <= arr.length - 1; i++) {
            System.out.println(arr[i]);
        }
    }

    @Test
    public void test3() {
        int[] arr = new int[]{1, 3, 4, 7, 12, 23, 67};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i <= arr.length - 1; i++) {
            System.out.println(arr[i]);
        }
    }

    @Test
    public void test4() {
        int[] arr = new int[]{1, 4, 7, 12, 23, 67};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i <= arr.length - 1; i++) {
            System.out.println(arr[i]);
        }
    }


    @Test
    public void test31() {
        int[] arr = new int[]{67, 23, 12, 7, 4, 1};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i <= arr.length - 1; i++) {
            System.out.println(arr[i]);
        }
    }

    @Test
    public void test41() {
        int[] arr = new int[]{67, 23, 12, 7, 4, 3, 1};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i <= arr.length - 1; i++) {
            System.out.println(arr[i]);
        }
    }

    public void quickSort(int arr[], int low, int high) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int l = low;
        int h = high;
        int key = arr[low];
        while (l < h) {
            while (l < h && arr[h] >= key) {//遇到第一个大于key的数字，跳出村换， 准备交换
                h--;
            }
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }

            while (l < h && arr[l] <= key) {//遇到第一个小于key的数字，跳出村换， 准备交换
                l++;
            }

            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
        System.out.print("low=" + (l + 1) + ",high=" + (h + 1) + ",key=" + key + "\n");
        //如果还没有交换完
        if (l > low) {
            quickSort(arr, low, l - 1);
        }
        if (h < high) {
            quickSort(arr, l + 1, high);
        }
    }
}
